1. Field of the Invention
The present invention generally relates to a codebook generating method and, more particularly, to a codebook generating method in use of image compression.
2. Description of the Related Art
Generally speaking, there are two ways of image compression: “lossy” compression and “lossless” compression. The lossy compression may produce an image with more distortion but achieve a high compression rate. The lossless compression may reconstruct an image without any distortion. However, the lossless compression can't achieve the high compression rate as the lossy compression. The image compression technique may be performed under two domains: frequency domain and spatial domain, as shown in Table 1 below:
TABLE 1Categories of Image CompressionLossy CompressionLossless CompressionFrequency DomainJPEGPNGSpatial DomainThe InventionGIF
For the lossy compression in spatial domain, a codebook is generally generated by a codebook generating method. The codebook has a smaller size than the original image and is thus used to replace the original image for image preservation and transmission. On the contrary, during the image decompression, the codebook is decoded by a decoding algorithm to obtain a plurality of reconstructed blocks. The reconstructed blocks are then combined into a reconstructed image for image decompression.
The conventional codebook generating method usually performs a dividing procedure on an original image to obtain a plurality of original blocks with smaller volume. The original blocks are then converted into a plurality of original vectors by a Vector Quantization mechanism. Finally, a decoding algorithm is used to decode the original vectors to obtain a plurality of code words. The code words have smaller quantity than the original blocks and are representative of the original image. Based on this, the codebook is constructed by the code words.
A conventional decoding algorithm such as a LBG algorithm was proposed by Linda, Buzo and Gray in 1980. The idea of the LBG algorithm is similar to the K-means method known in data clustering methods. In a first step of the LBG algorithm, a value of a distortion index ε, as well as a number K which the original vectors are to be grouped, are firstly defined. In a second step of the LBG algorithm, K original vectors are randomly selected from the plurality of original vectors to be centroids. In a third step of the LBG algorithm, a Euclidean distance between each original vector and centroid is calculated so that each original vector may be assigned to a corresponding centroid. In a fourth step of the LBG algorithm, a centroid of the original vectors in each group is determined and the determined centroid is defined as a new centroid. In a fifth step of the LBG algorithm, a difference between the new and old centroids in each group, namely, the distortion, is calculated. If the calculated distortion is not smaller than the value of the distortion index ε, the third step is repeated. If the calculated distortion is smaller than the value of the distortion index ε, the whole procedure is terminated. The finally obtained centroids may serve as the code words forming the codebook.
Generally, the aforementioned LBG algorithm initially is performed in a random manner. In addition, the original vectors are in larger number and more complex. Therefore, the obtained result of the LBG algorithm is somewhat unstable. Furthermore, the value of the distortion index ε is usually set smaller in order to have a better image quality. As a result, the condition of convergence is stricter, resulting in a slower training. Moreover, a longer training time period is resulted as every original vector requires calculation of the Euclidean distance.
Another conventional decoding algorithm such as Self-Organizing Map (SOM) is a non-monitoring artificial neural network proposed by Kohonen in 1980. In the SOM method, an artificial neural network consists of a plurality of neurons. The artificial neural network is used to train all the original pixels and adjust linking values thereof during the training. The training procedures are illustrated below.
In a first step of the SOM method, a difference between each original vector and neuron is calculated.
In a second step of the SOM method, the neuron having a smallest difference with a current original vector is determined, and the determined neuron is defined as a winning neuron.
In a third step of the SOM method, a weight linking value between the current original vector and the winning neuron is adjusted.
In a fourth step of the SOM method, the first to third steps are repeated until all original vectors are trained. Thus, a training cycle is finished. The SOM method is terminated when a predetermined number of times of training cycles are finished. By this time, a plurality of representative blocks forming the codebook is obtained.
The above SOMs coding algorithm requires a massive calculations to obtain a desired neural network. The more the original vectors or the neurons are, the longer the time period is required for calculations. Thus, a lower efficiency is resulted.
Another conventional hierarchical SOMs (HSOM) coding algorithm was proposed. The main idea of the HSOM method is dividing the calculations of the SOM method into two levels. For example, assume that there are 256 (16×16) neurons defined in the SOM method; in this case, the time complexity is higher. Based on this, the HSOM method firstly performs a first-level training on the original vectors using 16 neurons according to the SOM method, and then assigns the original vectors to the 16 neurons to obtain 16 groups of original vectors. Subsequently, the HSOM method performs a second-level training on each group of original vectors using 16 neurons according to the SOM method. Finally, 16 neurons are obtained in each group of original vectors. As a result, 256 neurons (16×16) are obtained and serve as the representative blocks forming the codebook, thus reducing the time complexity of the SOM method.
However, since each group has different number of original vectors but all the groups are trained using the same rather than different number of neurons during the second-level training, it is not easy to obtain the real distribution of the original vectors. Thus, a drawback of low efficiency is raised.
Based on the above problems, it is desired to improve the conventional codebook generating method.